package com.maozzi.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 衍生题
 *
 * @author maozi
 */
public class Other {
    public static void main(String[] args) {
//        System.out.println(findItinerary(new ArrayList<>(List.of(
//                        List.of("MUC", "LHR"),
//                        List.of("JFK", "MUC"),
//                        List.of("SFO", "SJC"),
//                        List.of("LHR", "SFO")
//                )))
//        );

        System.out.println(nQueens(4));
    }

    /**
     * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
     * <p>
     * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
     * <p>
     * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
     * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
     */
    public static List<String> findItinerary(List<List<String>> tickets) {
        tickets.sort(Comparator.comparing(o -> o.get(1)));
        List<String> list = new ArrayList<>();
        list.add("JFK");
        boolean[] used = new boolean[tickets.size()];
        findItinerary(list, used, tickets);
        return list;
    }

    public static boolean findItinerary(List<String> list, boolean[] used, List<List<String>> tickets) {
        if (list.size() == tickets.size() + 1) {
            return true;
        }
        for (int i = 0; i < tickets.size(); i++) {
            String from = tickets.get(i).get(0);
            String to = tickets.get(i).get(1);
            if (!used[i] && from.equals(list.get(list.size() - 1))) {
                used[i] = true;
                list.add(to);
                if (findItinerary(list, used, tickets)) {
                    return true;
                }
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
        return false;
    }

    /**
     * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
     * <p>
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * <p>
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     * <p>
     * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     */
    public static List<List<String>> nQueens(int n) {
        List<List<String>> list = new ArrayList<>();
        char[][] arr = new char[n][n];
        for (char[] c : arr) {
            Arrays.fill(c, '.');
        }
        nQueens(list, arr, n, 0);
        return list;
    }

    public static void nQueens(List<List<String>> list, char[][] arr, int n, int row) {
        if (row == n) {
            List<String> item = new ArrayList<>();
            for (char[] c : arr) {
                item.add(String.valueOf(c));
            }
            list.add(item);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isV(arr, row, i, n)) {
                arr[row][i] = 'Q';
                nQueens(list, arr, n, row + 1);
                arr[row][i] = '.';
            }
        }
    }

    private static boolean isV(char[][] arr, int row, int col, int n) {
        // 检查列
        for (int i = 0; i < row; i++) {
            if (arr[i][col] == 'Q') {
                return false;
            }
        }
        // 检查斜角
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (arr[i][j] == 'Q') {
                return false;
            }
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (arr[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
